package main

import "fmt"

/*
最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
*/

//自己想的 排序->去重->算
/*
func quick(n []int) {
	if len(n) <= 1 {
		return
	}
	l, r, key := 0, len(n)-1, n[0]
	for i := 1; i <= r; {
		if key < n[i] {
			n[i], n[r] = n[r], n[i]
			r--
		} else {
			n[i], n[l] = n[l], n[i]
			i++
			l++
		}
	}
	quick(n[:l])
	quick(n[l+1:])
}

func del(n []int) []int {
	if len(n) <= 1 {
		return nil
	}
	l, r := 0, 0
	for r < len(n) {
		if n[l] != n[r] {
			l++
			n[l] = n[r]
		}
		r++
	}
	return n[:l+1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func longestConsecutive(nums []int) int {
	quick(nums)
	nums = del(nums)
	if len(nums) <= 1 {
		return len(nums)
	}
	l, r := 0, 1
	var res, cur = 0, 1
	for r < len(nums) {
		if nums[r]-nums[l] == 1 {
			cur++
			res = max(res, cur)
		} else {
			res = max(res, cur)
			cur = 1
		}
		l++
		r++
	}
	return res
}
*/

//哈希
func longestConsecutive(nums []int) (res int) {
	hash := make(map[int]bool)
	for _, v := range nums {
		hash[v] = true
	}
	for _, v := range nums {
		if hash[v+1] {
			continue
		}
		cur, cnt := v, 0
		for hash[cur] {
			cnt++
			hash[cur] = false
			cur--
		}
		if cnt > res {
			res = cnt
		}
	}
	return
}

func main() {
	n := []int{100, 4, 200, 1, 3, 2, 2}
	fmt.Println(longestConsecutive(n))
}
